Fundamentals of Computer Graphics, Image Processing, and Vision¶

Exercise 2: Epipolar Geometry¶

In this exercise you will explore estimating the relationship between two camera views using the epipolar geometry concepts learned in the lectures.

NOTE: When submitting the Colab notebook, please remove any unnecessary/debug cells. That is, your notebook should be clean to make it easy for the grader to follow.

---

Student 1:
Name: Rony Kositsky ID: 205817893

Student 2:
Name: Yonatan Gartenberg ID: 311126205

---

Part 1: Fundamental Matrix Estimation¶

Recall that we are interested in solving the correspondence problem. Specifically, given two images taken from cameras at different positions. How do we match a point in the first image to a point in the second image?

We have seen that it is possible to learn a mapping of points in one image to lines in another image using the Fundamental Matrix.

To do so, we have provided you with two scenes.

• In the first scene, sceneA, we have provided you with corresponding point locations listed in sceneA-pts2d-1.txt and sceneA-pts2d-2.txt.
• In the second scene, sceneB, we ask you to compute the corresponding points yourself. Please use the provided utility script tag_image.py to do so.

---

Hint: When solving for the fundamental matrix $F$, think about how many correpsonding points we need. What happens if we have more pairs than required?

Question 1¶

Write a function that computes the Fundamental Matrix $F$ that satisfies the epipolar constraints defined by the sets of corresponding points using least squares.

---

Recall that $F$ is only known up to a scale factor. To make sure that your code is correct, if you solved for $F$ correctly, you should get a matrix that is a scaled equivalent to the following for sceneA:

 F =  [[ 2.67713722e-07 -2.57763422e-06  1.12898577e-03]
       [ 7.43898031e-06  3.90196194e-06  7.31449001e-03]
       [-2.43366396e-03 -1.14515247e-02  1.00000000e+00]] 

Question: Notice that the least squares estimate of $F$ is of full rank. However, the Fundamental Matrix should be a matrix of rank $2$. Why is the fundamental matrix of rank $2$? (We require you to show only the upper bound. That is, that $F$ is not of full rank).

Answer: We calculated F from the equation $x_r^TFx_l = 0$. We can conclude that the right epipolar line lies on the surface of $Fx_l$, and therefore, it holds that $e_r^TFx_l = 0$. From simetry we can prove the same equation for the left epipolar line $e_l$. We can deduce that F has a non-zero eigenvector corresponding with a zero eigenvalue.Therefore, F's rank <= F's dimesion -1. We used F with a dimension=3, so the upper bound for the rank is 2.

---

Question 2¶

From the proof you provided above, $F$ should be of rank 2. Therefore, we must reduce the rank of the estimated $F$. To do so, we can decompose $F$ using singular value decomposition (SVD) into the matrices $U\Sigma V^T = F$. We can then estimate a rank 2 matrix by setting the smallest singular value in $\Sigma$ to zero thus generating $\Sigma'$. The Fundamental Matrix is then easily calculated as $F=U\Sigma 'V^T$.

Compute the fundamental matrix $F$ of rank 2 using SVD as described above.

---

Question 3¶

Given our fundamental matrix $F$ of rank 2, we can now compute the epipolar line $\ell_b$ in image $B$ corresponding to a point $p_a$ in image $A$: $\ell_b = Fp_a$

A similar equation can be used for computing the epipolar lines in image $A$.

You are now tasked with drawing these epipolar lines.

Observe that drawing the epipolar lines on the image plane is not trivial. This is because the lines $\ell_i$ are defined in homogeneous coordinates whereas the standard line function takes two input points.

In order to find two such points, we can find the intersection of a given line $\ell_i$ with the image boundaries.

To do so, we need to compute two things:

• The line $\ell_L$ corresponding to the left-hand side of the image.
• The line $\ell_R$ corresponding to the right-hand side of the image.

Once, we have these lines, we can compute the intersection point $P_{i,L}$ between $\ell_i$ and $\ell_L$ and intersection point $P_{i,R}$ between $\ell_i$ and $\ell_R$.

Once we have these two points, we can compute the line running through the points $P_{i,L}$ and $P_{i,R}$.

---

To summarize, in this question you are required to compute the following:

1. The lines corresponding to the left-hand and right-hand boundaries of the image.
2. The intersection point between the image boundaries and the given epipolar line.

After computing these lines, you should draw the estimated epipolar lines on each of the two images. For each scene, please display the two images side-by-side with the epipolar lines drawn on each.

---

Hint: The intersection between two lines $l_1$ and $l_2$ is a point $p$ in homogeneus coordinates s.t. $p\cdot l_1=0$ and $p\cdot l_2=0$, that is a point $p$ which is perpendicular to both $l_1$ and $l_2$.

---

Question 4: BONUS (5-10pts)¶

Take a look at the results of the last section. You may notice that the epipolar lines are not exact.

The problem here is that the offset and scale of the points is large and biased compared to some of the constants. To fix this, we can normalize the points.

Specifically, we want to construct a transformation $T$ that will make the mean of the points $0$ and scale the points to magnitude $1$. In other words, we wish to find: $$ \begin{equation*} \begin{pmatrix} {u'} \ {v'} \ {1} \

\end{pmatrix}¶

$$\begin{pmatrix} {s} & {0} & {0} \\ {0} & {s} & {0} \\ {0} & {0} & {1} \\ \end{pmatrix}$$ $$\begin{pmatrix} {1} & {0} & {-c_u} \\ {0} & {1} & {-c_v} \\ {0} & {0} & {1} \\ \end{pmatrix}$$ $$\begin{pmatrix} {u} \\ {v} \\ {1} \\ \end{pmatrix}$$

\end{equation*} $$

The transform matrix $T$ is the product of the scale and offset matrices. Notice that $c_u, c_v$ are simply the mean of the points. To compute the scale $s$ you can first estimate the standard deviation after subtracting the means of the points. Then, $s$ can be defined as the reciprocal of the standard deviation.

---

Create two matrices $T_a$ and $T_b$ for the set of points defined in the files sceneB-pts2d-1.txt and sceneB-pts2d-2.txt, respectively.

Then, normalize the two sets of points to compute the new normalized fundamental matrix $\hat F$.

Note: make sure that $\hat F$ is of rank $2$!

(You only need to complete this for sceneB using the points provided to you)

Part 2: Finding the Correspondences¶

Up to now, we've only discussed how one can compute the epipolar lines between two images.
In this section, we use a window-based approach for estimating dense stereo correspondence.

For this part, we will be working with the images named corr-img-l.png and corr-img-r.png found in input/correspondences.

Here, you will implement the stereo alogrithm and take a window around every pixel in one image and search for the best match in the other image. This concept is discussed in the class lecture (~slides 58-68).

The basic algorithm is defined as follows:

1. For each epipolar line / horizontal scan line:
   a. For each pixel $p$ on the left line:
   1. Compare a window around $p$ with same window shifted along the same horizontal scan line in the other image.
   2. Pick location corresponding to the best matching window.

To help simplify the problem, we will assume that the two images are aligned horizontally. Therefore, when performing the matching, you only need to scan across the same horizontal scan line of the other image.

When computing the similarities, we will use the sum of squared differences (SSD) measure.

---

Question 1: Implementing SSD for Computing Disparity Map¶

Implement the SSD matching algorithm. The algorithm returns a disparity image $D$ where

$$\begin{equation} L(y,x) = R(y,x+D(y,x)) \end{equation}$$ when matching from the left image to the right image, denoted by $L$ and $R$, respectively.

Then, repeat this for matching from the right image to the left image. That is, you should output two images:

1. $D_L = disparity(L,R)$
2. $D_R = disparity(R,L)$

Then, change the values of:

1. The window size
2. The disparity range (i.e., the maximum number of pixels to slide the window over)

How does changing these values affect the results? Please clearly display and label the results in the notebook with the two disparity maps shown side-by-side.

Some notes to consider:

• When computing the SSD between the two window patches, you may use cv2.matchTemplate and cv2.TM_SQDIFF_NORMED.
• We provide you the ground truth images to allow you to compare your results. Don't worry if you don't get something similar to the ground truths.
• If you see that the execution time takes a long time, you may want to consider down-sampling the input images. Hint: use cv2.pyrDown().

When displaying the images, please display them in grayscale!

Hint: To verify that your implementation is correct, think about the values you should obtain closer to the camera. Larger values should be shown in white with lower values shown in black.

After computing the disparity maps, you should display the results side-by-side, which can be done using the follow cell as a reference. Please note that when displaying the results you should clearly specify the parameters used to obtain the results!

Question: How does changing the value of the window size affect the results? How does changing the value of the maximum disparity range affect the results?
Answer: After exploring a vast range of otions we've come to a conclusion that the window size and the disparity range are linked.

Separately, keeping the disparity range at 250, if we use very low values of the window size (around ~2), the result contains a lot of small noise, yet the details of the picture remain "sharp". If we use high values of the window size (around ~15), the result is less noisy, but the details appear to be blunt.

Regarding the disparity range, keeping the window size at 6 - If we use very low values (around ~120), there is also noise, and the smaller details of the pictures are distorted, where the bigger ones are more "in tact". If we use very high values (around ~300), the details are clearer, but the differences that suppose to be between close and far objects, are very small to distinct (i.e. the gray hues are very similar)

We conclude there is a "sweet spot" of the two. In oure case we achived it around window size = 6, and disparity range = 250

---

Question 2: Analyzing the SSD Metric¶

Above we used SSD to compute the correspondences. However, SSD is not robust to small changes in the image.

Here, we will explore the sensitivity of SSD to small changes in the images. Specifically, repeat Question 1, but with the following changes:

1. Add Gaussian noise to one or both of the images. Visualize the resulting inputs to make sure the noise is visible. Then, run the matching algorithm with SSD again.
2. Add contrast to one of the images and re-run the SSD matching algorithm. (changing the contrast means multiplying the pixel values by some constant factor)

Display the results of both of the variations. What happened to the results?

Question: Why is SSD sensitive to Gaussian noise? Why is it sensitive to changes in contrast?
Answer: SSD is sensitive to gaussian noise because it "masks" the most of the picture, meaning that now with the noise in place, the measured distance between 2 pixels in 2 "picture windows" is more likely to get false results, because now the minimum distance is less likely to be the same as the one that would be measured withput the noise.

Regarding the contrast, the sensitivity is originated in the fact that only one picture is "contrasted", thus bringing a large amount of pixels to "saturation", turning bright pixels dark, and vice versa. This phenomena makes it nearly impossible for the SSD to find the matching pixel in the other image.

---

Question 3: Implementing Normalized Cross Correlation (NCC) for Computing Disparity Map¶

We have now seen that the SSD metric is not robust to small changes between the input images. Therefore, in this section we will compute the correspondences using the Normalized Cross Correlation (NCC) metric introduced in class.

Repeat Questions 1 and 2 where now, NCC is used for computing the similarity between two window patches. As before, you may use cv2.matchTemplate for computing the similarity.

Again, explore different values for the window size and maximum disparity.

Think to yourself: how did the NCC measure affect the results when adding Gaussian noise? How about when changing the contrast? Do your results make sense?